package com.github.yangyishe.p200;

/**
 * 137. 只出现一次的数字 II
 * https://leetcode.cn/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 *
 * 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,2,3,2]
 * 输出：3
 * 示例 2：
 *
 * 输入：nums = [0,1,0,1,0,1,99]
 * 输出：99
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * -231 <= nums[i] <= 231 - 1
 * nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 */
public class Problem137 {
    public static void main(String[] args) {
        int[] nums=new int[]{2,2,3,2};

        Problem137 problem137 = new Problem137();
        int singleNumber = problem137.singleNumber(nums);
        System.out.println("singleNumber = " + singleNumber);

    }

    /**
     * 思路:
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        //1. 创建一个位数-值对应表,值只能为0,1,2
        char[] bits=new char[32];

        //2. 每次遍历, 都对该数组对应位数+1.如果=3,则置0
        for(int n:nums){
            for(int i=0;i<32;i++){
                if ((n&(1<<i))!=0) {
                    bits[i]++;
                    if(bits[i]==3){
                        bits[i]=0;
                    }
                }
            }
        }

        //3. 将对应表转化为数字
        int r=0;
        for(int i=31;i>=0;i--){
            r=(r<<1)|(bits[i]);
        }

        return r;
    }
}
